// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef __HIERARCHICALGRID3D_H_INCLUDED__
#define __HIERARCHICALGRID3D_H_INCLUDED__

#include "IWriteFile.h"
#include "IReadFile.h"
#include "Core/Commons.h"

using namespace irr;

template<typename T, T EmptyValue>
class HierarchicalGrid3dNode
{
public:
	enum EType
	{
		k_typeNull = 0,
		k_typeGrid,
		k_typeQuad,
	};

public:
	HierarchicalGrid3dNode()
	{
	}

	virtual ~HierarchicalGrid3dNode()
	{
	}

	virtual s32 GetType() const = 0;
	virtual T Get(s32 x, s32 y, s32 z) const = 0;
	virtual void Export(irr::io::IWriteFile& stream) const = 0;
};

template<typename T, T EmptyValue>
class HierarchicalGrid3dNode_Grid : public HierarchicalGrid3dNode<T,EmptyValue>
{
public:
	HierarchicalGrid3dNode_Grid(T* data, s32 stridex, s32 stridey, s32 sx, s32 sy, s32 sz) :
		HierarchicalGrid3dNode<T,EmptyValue>(),
		m_sx(sx),
		m_sy(sy),
		m_sz(sz),
		m_grid(0)
	{
		m_grid = NEW T[m_sx * m_sy * m_sz];
		for(s32 z = 0; z < m_sz; ++z)
		{
			for(s32 y = 0; y < m_sy; ++y)
			{
				for(s32 x = 0; x < m_sx; ++x)
				{
					m_grid[(z * m_sy + y) * m_sx + x] = data[(z * stridey + y) * stridex + x];
				}
			}
		}
	}

	virtual ~HierarchicalGrid3dNode_Grid()
	{
		SAFE_DEL_ARRAY(m_grid);
	}

	virtual s32 GetType() const
	{
		return HierarchicalGrid3dNode<T,EmptyValue>::k_typeGrid;
	}

	virtual T Get(s32 x, s32 y, s32 z) const
	{
		ASSERT(0 <= x && x < m_sx);
		ASSERT(0 <= y && y < m_sy);
		ASSERT(0 <= z && z < m_sz);
		return m_grid[(z * m_sy + y) * m_sx + x];
	}

	HierarchicalGrid3dNode_Grid(irr::io::IReadFile& stream) :
		HierarchicalGrid3dNode<T,EmptyValue>(),
		m_sx(-1),
		m_sy(-1),
		m_sz(-1),
		m_grid(0)
	{
		stream.read(&m_sx,sizeof(s16));
		stream.read(&m_sy,sizeof(s16));
		stream.read(&m_sz,sizeof(s16));
		
		m_grid = NEW T[m_sx * m_sy * m_sz];
		stream.read(m_grid, m_sx * m_sy * m_sz * sizeof(T));
	}

	virtual void Export(irr::io::IWriteFile& stream) const
	{
		stream.write(&m_sx, sizeof(m_sx));
		stream.write(&m_sy, sizeof(m_sy));
		stream.write(&m_sz, sizeof(m_sz));
		stream.write(m_grid, m_sx * m_sy * m_sz * sizeof(T));
	}

	s16 m_sx;
	s16 m_sy;
	s16 m_sz;
	T* m_grid;
};


template<typename T, T EmptyValue>
class HierarchicalGrid3dNode_Quad : public HierarchicalGrid3dNode<T,EmptyValue>
{
public:
	enum EScanResult
	{
		k_empty = 0,
		k_mixed,
		k_full,
	};
public:
	HierarchicalGrid3dNode_Quad(T* data, s32 stridex, s32 stridey, s32 sx, s32 sy, s32 sz) :
		HierarchicalGrid3dNode<T,EmptyValue>(),
		m_sx0(sx / 2),
		m_sy0(sy / 2),
		m_sz0(sz / 2)
	{
		s32 sxs[2];
		s32 sys[2];
		s32 szs[2];
		sxs[0] = m_sx0;
		sxs[1] = sx - m_sx0;
		sys[0] = m_sy0;
		sys[1] = sy - m_sy0;
		szs[0] = m_sz0;
		szs[1] = sz - m_sz0;

		for(s32 k = 0; k < 2; ++k)
		{
			for(s32 j = 0; j < 2; ++j)
			{
				for(s32 i = 0; i < 2; ++i)
				{
					s32 x = i * m_sx0;
					s32 y = j * m_sy0;
					s32 z = k * m_sz0;
					HierarchicalGrid3dNode<T,EmptyValue>* node;
					if (sxs[i] && sys[j] && szs[k])
					{
						node = CreateNode(data + (z * stridey + y) * stridex + x, stridex, stridey, sxs[i], sys[j], szs[k]);
					}
					else
					{
						node = 0;
					}
					nodes[(k * 2 + j) * 2 + i] = node;
				}
			}
		}
	}

	virtual ~HierarchicalGrid3dNode_Quad()
	{
		for(s32 i = 0; i < 8; ++i)
		{
			SAFE_DEL(nodes[i]);
		}
	}

	virtual s32 GetType() const
	{
		return HierarchicalGrid3dNode<T,EmptyValue>::k_typeQuad;
	}

	virtual T Get(s32 x, s32 y, s32 z) const
	{
		s32 i = (x < m_sx0) ? 0 : 1;
		s32 j = (y < m_sy0) ? 0 : 1;
		s32 k = (z < m_sz0) ? 0 : 1;
		HierarchicalGrid3dNode<T,EmptyValue>* node = nodes[(k * 2 + j) * 2 + i];
		if (!node)
		{
			return EmptyValue;
		}
		x = x - i * m_sx0;
		y = y - j * m_sy0;
		z = z - k * m_sz0;
		return node->Get(x, y, z);
	}

	HierarchicalGrid3dNode_Quad(irr::io::IReadFile& stream) :
		HierarchicalGrid3dNode<T,EmptyValue>(),
		m_sx0(-1),
		m_sy0(-1),
		m_sz0(-1)
	{
		stream.read(&m_sx0, sizeof(s16));
		stream.read(&m_sy0, sizeof(s16));
		stream.read(&m_sz0, sizeof(s16));
		
		for(s32 i = 0; i < 8; ++i)
		{
			s8 type;
			stream.read(&type, sizeof(s8));
			if (type == HierarchicalGrid3dNode<T,EmptyValue>::k_typeNull)
			{
				nodes[i] = 0;
			}
			else if (type == HierarchicalGrid3dNode<T,EmptyValue>::k_typeGrid)
			{
				nodes[i] = NEW HierarchicalGrid3dNode_Grid<T,EmptyValue>(stream);
			}
			else if (type == HierarchicalGrid3dNode<T,EmptyValue>::k_typeQuad)
			{
				nodes[i] = NEW HierarchicalGrid3dNode_Quad<T,EmptyValue>(stream);
			}
			else
			{
				ASSERT(false);
			}
		}
	}
		
	virtual void Export(irr::io::IWriteFile& stream) const
	{
		stream.write(&m_sx0, sizeof(m_sx0));
		stream.write(&m_sy0, sizeof(m_sy0));
		stream.write(&m_sz0, sizeof(m_sz0));
		for(s32 i = 0; i < 8; ++i)
		{
			s8 type = nodes[i] ? nodes[i]->GetType() : HierarchicalGrid3dNode<T,EmptyValue>::k_typeNull;
			stream.write(&type, sizeof(type));
			if (type == HierarchicalGrid3dNode<T,EmptyValue>::k_typeNull)
			{
				ASSERT(nodes[i] == 0);
			}
			else
			{
				nodes[i]->Export(stream);
			}
		}
	}

	static EScanResult ScanNode(T* data, s32 stridex, s32 stridey, s32 sx, s32 sy, s32 sz)
	{
		s32 countEmpty = 0;
		s32 countFull = 0;
		for (s32 z = 0; z < sz; ++z)
		{
			for (s32 y = 0; y < sy; ++y)
			{
				for (s32 x = 0; x < sx; ++x)
				{
					if (data[(z * stridey + y) * stridex + x] != EmptyValue)
					{
						++countFull;
					}
					else
					{
						++countEmpty;
					}
				}
			}
		}
		if (countFull == 0)
		{
			return k_empty;
		}
		s32 count = countFull + countEmpty;
		s32 mixedSize = countFull * sizeof(T) + 8 * sizeof(HierarchicalGrid3dNode_Grid<T,EmptyValue>) + sizeof(HierarchicalGrid3dNode_Quad<T,EmptyValue>);
		s32 fullSize = count * sizeof(T);
		if (fullSize < mixedSize)
		{
			return k_full;
		}
		return k_mixed;
	}

	static HierarchicalGrid3dNode<T,EmptyValue>* CreateNode(T* data, s32 stridex, s32 stridey, s32 sx, s32 sy, s32 sz)
	{
		EScanResult scan = ScanNode(data, stridex, stridey, sx, sy, sz);
		if (scan == k_mixed)
		{
			return NEW HierarchicalGrid3dNode_Quad<T,EmptyValue>(data, stridex, stridey, sx, sy, sz);
		}
		else if (scan == k_full)
		{
			return NEW HierarchicalGrid3dNode_Grid<T,EmptyValue>(data, stridex, stridey, sx, sy, sz);
		}
		ASSERT(scan == k_empty);
		return 0;
	}

	s16 m_sx0;
	s16 m_sy0;
	s16 m_sz0;
	HierarchicalGrid3dNode<T,EmptyValue>* nodes[8];
};

template<typename T, T EmptyValue>
class HGrid3d : public HierarchicalGrid3dNode_Quad<T,EmptyValue>
{
public:
	HGrid3d(T* data, s32 stridex, s32 stridey, s32 sx, s32 sy, s32 sz) :
		HierarchicalGrid3dNode_Quad<T,EmptyValue>(data, stridex, stridey, sx, sy, sz)
	{
	}

	HGrid3d(irr::io::IReadFile& stream) :
		HierarchicalGrid3dNode_Quad<T,EmptyValue>(stream)
	{
	}
};

#endif
